1. Field of the Invention
The present invention is related to a method and system to be utilized in data communications involving at least one data communications network.
2. Description of the Related Art
Data communications is the transfer of data from one or more sources to one or more sinks that is accomplished (a) via one or more data links between the one or more sources and the one or more sinks (b) according to a protocol. A data link is the means of connecting communications facilities or equipment at one location to communications facilities or equipment at another location for the purpose of transmitting and receiving data. A protocol, in communications, computer, data processing, and control systems, is a set of formal conventions that govern the format and control the interactions between at least two communicating functional elements in order to achieve efficient and understandable communications. Examples of protocols are Asynchronous Transfer Mode (ATM) protocol, Internet Protocol (IP), and Transport Control Protocol (TCP).
A data communications network is the interconnection of three or more network stations, (each network station functioning as a data source and/or sink) over one or more data links, which allows communication between the three or more network stations over the one or more data links. A packet-switched data communications network is a network in which data is transmitted and routed through the network in the form of packets. A packet is a sequence of bits that includes data and control signals, where typically the control signals appear in a header part—a sequence of bits forming a first part of the packet—and the data appear in data part—a sequence of bits forming a second part of the packet. In packet-switched networks, data communications network stations (e.g., routers, bridges, gateways, clients, servers, etc.) may be implemented by a variety of techniques, such as software application programs running on interconnected computer systems, Application Specific Integrated Circuits (ASICs), or combinations of software and ASICs implemented within interconnected computer systems. (e.g., the Cisco Systems® Catalyst® family of switches and the Cisco 7xxx family of routers).
As noted, a data communications network is the interconnection of three or more network stations (each network station functioning as a data source and/or sink) over one or more data links. However, within the context of packet-switched networks, the convention within the art is to add to the foregoing definition the additional requirement that the defined packet-switched data communications network be under the control of a defined network administrator—an entity (usually a person or group of persons) responsible for and having ultimate control over a defined group of network stations. Following this convention, when a first defined packet-switched network is connected to a second defined packet-switched network via at least one network station common to both the first defined and second defined networks, such a configuration is conventionally referred to as an “internetwork”—a short hand notation for the phrase “interconnected network of networks.” Note that this convention recognizes that two or more networks have been interconnected, but also recognizes that the totality of such interconnected networks itself forms a network. Thus, while the following detailed description describes devices and processes in the context of a network, such detailed description is also equally applicable to internetworks.
As networks, and networks of networks (e.g., the Internet) proliferate, increasing attention is being paid to problems involving network security (e.g., controlling which network stations can communicate with each other). For example, for a commercial lending bank having an intranet (a private network belonging to the bank) which has one or more network stations connected to the Internet, it is common for the bank's network administrator to want to ensure that the only network stations that have access into and out of the bank's intranet are clearly defined and closely controlled. In addition, it is also common for the network administrator to restrict access between various network stations of the bank's intranet. One way that this is conventionally done is to restrict which packets can pass through each network station over which the bank's network administrator has control. In this technique, each network station examines header information of received packets in order to determine how to dispose of the packets (e.g., whether to accept, transmit, reject, or forward the received packets). By controlling, on the basis of information contained in received packet headers, which packets can pass which network stations, the network administrator is able to control access to various parts of his network on either side of each network station. Accordingly, this technique is known in the art as packet level access control.
In the packet-level access control technique, lists of rules are used by each network station to determine which received data packets to accept, transmit, forward, or reject. Since these rules control access to various portions of a network (or more or more internetworks), such rules are conventionally referred to as Access Control Rules. The complete set of rules maintained by an individual network station is conventionally known as an Access Control List (ACL).
An ACL is a set of rules for determining how a network station should dispose of various received packets. ACL rules are typically an ordered list of plain English rules which have been translated into the grammar and syntax understood by the network station where the ACL is to be implemented (e.g., expressed such that the network operating system can interpret and effect the desires expressed in the ordered list of plain English rules). For example, the plain English rule of “Permit TCP packets from any source to host with IP address equal to 194.121.68.173 and TCP port number greater than 1023” can be expressed in network station understandable grammar and syntax as “permit TCP any host 194.121.68.173 GT 1023” (expressed here for sake of example in a grammar and syntax understandable by a network server computer running Cisco Systems' IOS (Internetworking Operating System), but also expressible in other network operating system or computer operating system formats). ACLs can become quite complex and can grow to thousand upon thousands of rules.
When a data packet is received by a network station which disposes of received packets on the basis of an ACL, the packet's header information must be compared against those ACL rules which utilize the information contained within the received packet's header in order to make access control decisions. In addition, such comparisons should be done in the sequential order in which the rules appear in the ACL, since the order in which the rules are arranged in an ACL typically encodes important control information (e.g., if an ACL has a first-in-sequence rule that states “permit packets from source address Memphis to destination address San Francisco,” and a second-in-sequence rule that states “deny packets from source address Memphis to any destination address,” if the order of evaluation is reversed, the packet from Memphis to San Francisco will never get through the network station).
For an ACL with a relatively small number of rules, comparing a packet's header against the ACL rules causes very little network traffic delay. However, as the number of rules in an ACL grows, the delay associated with comparing packet headers against the ACL rules can be very computationally intensive, and can result in significant network traffic delay above and beyond that associated with smaller ACLs.
While it may seem reasonable that ACLs with a relatively large number of rules will result in significant network delay above and beyond that associated with ACLs with a relatively smaller number of rules, those skilled in the art will recognize that network administrators prefer that adding rules to ACLs maintained by network stations not result in noticeable performance degradation of those network stations.
Techniques exist within the art which provide network stations with the ability to maintain relatively larger ACLs without noticeable degradation of performance over relatively smaller ACLs, but those techniques are not practicable for many situations. For example, some of the most successful techniques have involved a faster and more compact method of converting the ACL rule elements into entries in a content-addressable memory (CAM), but such techniques tend to add overhead to the systems. Furthermore, insofar as that the CAM-based techniques involve a radical design departure from older-generation systems, the newer CAM-based network stations are generally not backwards-compatible with existing network stations.
In many situations, network administrators are dissatisfied with the ACL-related performance of their network stations, but such network administrators have either concluded that the problems are not severe enough to warrant investing in the newer CAM-based network stations, or such network administrators cannot afford the newer CAM-based network stations. In addition, many network station vendors have invested significant research and development funds into their current-generation network stations, and would prefer to extend the life of such current-generation network stations before adopting the radical redesign needed to move to the newer-generation CAM-based network stations. One way of extending the life of such current-generation network stations would be to improve the ability of such network stations to handle relatively long ACLs.
It is therefore apparent that a need exists for a method and system which will provide improved ACL performance for network stations in a relatively cost-effective manner (e.g., in a manner not requiring the use of expensive CAM-based technology). In addition, a need further exists for a method and technique which is substantially backwards-compatible with existing ACL systems, which will thus allow vendors to retro-fit network stations already purchased by customers, and also allow vendors to further extend the life of their current-generation network stations.
The foregoing general discussion of the related art can be supplemented by reference to the following texts, all of which are hereby incorporated by reference in their entireties: Merilee Ford, et. al., Internetworking Technologies Handbook, Cisco Press 1997; Karanjit S. Siyan, Inside TCP/IP, 3d ed., New Riders Publishing 1997; Internet Firewalls and Network Security, 3d ed., New Riders Publishing 1995; D. Brent Chapman and Elizabeth D. Zwicky, Building Internet Firewalls, O'Reilly & Associates, 1995; Network Protocols Configuration Guide, Cisco IOS® Release 12.0, Cisco Press, 1998; and Network Protocols Command Reference, IOS Release 12.0, Cisco Press, 1998.
Cisco Systems, Cisco IOS, and Catalyst are registered trademarks of Cisco Systems, Inc. of San Jose, Calif.